\documentclass[a4paper,11pt]{article}

\usepackage{fontspec} %支持文章中字体配置
\usepackage{amsmath} %支持更多数学格式
\usepackage{xcolor,graphicx} %支持插入图片


\setlength{\hoffset}{-60pt} %左边界
\setlength{\textwidth}{480pt} %正文宽度
\setlength{\voffset}{-70pt} %上边界
\setlength{\textheight}{650pt} %正文长度

\linespread{1.2}

\newtheorem{definition}{定义}
\newtheorem{theorem}{定理}
\newtheorem{lemma}{引理}

% Configure zh font in {}
% use the following command to see available Chinese fonts.
% fc-list :lang=zh
\setmainfont{WenQuanYi Zen Hei}

% 中文自动换行
\XeTeXlinebreaklocale "zh"

% Main text %
\author{曹金}
\date{}

\title{<<Decoding by Linear Programming>>主要结论}

\begin{document}

\maketitle
\tableofcontents

\section{主要内容}

文章~\cite{candes_decoding_2005}中定义了限制等距常数(Restricted Isometry Constants), 并且当该常数满足一定条件, 就能通过线性规划的方法准确地恢复出稀疏向量. 限制等距常数在压缩感知中是一个重要的参数, 它在不同的条件下可以相应得到不同性能的结果.

\section{数学模型}
\label{sec:model}

\[
y = Af + e,
\]
其中, $f \in R^n, y \in R^m, A \in R^{m \times n}, m > n$.
我们将$f$看作是为线性码编码前的信息位, $Af$作为编码后的码字, 通过信道传输后有错误$e$加入, 得到有错误的码字$y$. 如果错误向量$e$非零值较大的话, 显然$f$就很难准确恢复了. 如果出错的位数不多, 即向量$e$中的非零值不多, 我们可以将它看作的是一个稀疏信号. 

现在用下面的方法尝试准确恢复$f$. 构造矩阵$F$, 使$FA = 0$, 这样可以得到$ \tilde{y} = Fy = F(Af + e) = FAf + Fe = Fe $, 如果我们能够求的$e$, 则原信息码可以通过$f = A^{-1}(y - e)$得到. 现在问题转化为通过
\[
\tilde{y} = Fe
\]
已知观测矩阵$F$和观测向量$\tilde{y}$, 来恢复稀疏信号e.

\section{记号和概念}
\label{sec:notation}
现在给出在后面的部分中出现的符号所表示的含义.

记号$ \| \cdot \| $表示向量2范数$ \| \cdot \|_{\ell_2} $

$ F = (v_1, v_2, \dots, v_n) \in R^{p \times n}, \quad \text{设}J = \{1,2,\dots,n\}, \quad |J| = n $

$ F_T = \sum_{j \in T} c_j v_j \in H, \quad T \subseteq J, \quad H$表示所有F的列向量张成的空间.

S表示向量的稀疏度, 即在向量中有S个非零值. 在这篇文章中又可以看作是向量中出现S个错误.

\subsection{支撑集(support set)}
\label{sec:supp}

实值函数f的支撑集, 指的是所有使$f(t) \neq 0 $的所有的t的集合. 例如, 对于向量来说, $a = (0, 3, 9, 0, 3, 0, 0, 1, 0)^T \in R^9$的支撑集为$ T = \{2,3,5,8\} $.

\section{定义}
\label{sec:definition}

设F是由有限个向量$ (v_j)_{j \in J} \in R^p $做为它的列向量所构成的, 对于每个$ 1 \le S \le |J| $, 
\begin{definition}[限制等距常数(Restricted Isometry Constants)]
  S限制等距常数(S-restricted isometry constants)$ \delta_S $是一个较小的常数,  使$ F_T $满足:
  \begin{equation}
    \label{eq:delta}
    (1 - \delta_S) \| c \|^2 \le \| F_T c \|^2 \le (1 + \delta_S) \| c \|^2
  \end{equation}
  对于所有的子集$ T \subset J, |T| \le S $, 和所有的实系数$ (c_j)_{j \in T}$.
\end{definition}

\begin{definition}[限制正交常数(S,S'-restricted orthogonality constants)]
  S,S'限制正交常数(S,S'-restricted orthogonality constants)$ \theta_{S,S'} $是一个较小的常数, 对于$ S + S' \le |J| $, 使$ F_T $满足:
  \begin{equation}
    \label{eq:theta}
    |\left< F_T c, F_{T'} c' \right> | \le \theta_{S,S'} \cdot \| c \| \| c' \|
  \end{equation}
  对于不相交的$ \forall T, T' \subseteq J$, 且 $|T| \le S, |T'| \le S$.
\end{definition}

值得注意的是, 这两个常数都是关于矩阵F的一个参数, 即对于矩阵F给出了参数$ \delta_S, \theta_{S,S'} $, F就能够分别满足(~\ref{eq:delta})(~\ref{eq:theta}).

\section{主要结论}
\label{sec:conclusion}

\begin{lemma}
  \label{deltaandtheta}
  对于$ \forall S, S' $有下面的关系式:
  \[
  \theta_{S, S'} \le \delta_{S + S'} \le \theta_{S, S'} + \max (\delta_S, \delta_{S'})
  \]
\end{lemma}


\begin{lemma}
  \label{unique}
  设$ T \subset J, |T| \le S, f := Fc $, 其中c是任意支撑于集合T(参见~\ref{sec:supp})的向量. 假设$ S \ge 1 $且$ \delta_{2S} < 1 $, 则c可以唯一地由下式的最小化解得到.
  \[
  (P_0) \quad \min \| d \|_{\ell_0} \quad s.t.\quad Fd = f
  \]
\end{lemma}

根据上面的引理, 只要有$ \delta_{2S} < 1 $, 就可以通过向量f唯一地还原出的向量c, 方法
是求满足$ (P_0) $的最小化解.


\begin{theorem}
  \label{th:theorem1}
  设$ f := Fc $, $ c \in R $支撑于集合$ T \subset J $, 且$ |T| \le S $. 假设$S \ge 1 $, 且$ \delta_S, \theta_{S,S}, \theta_{S,2S} $满足下面的条件
  \begin{equation}
    \label{eq:theorem1}
    \delta_S + \theta_{S,S} + \theta_{S,2S} < 1
  \end{equation}
  则c就是下面优化问题唯一的最小解
  \[
  (P_1) \quad \min \| d \|_{\ell_1} , \quad s.t. \quad Fd = f.
  \]
\end{theorem}

可以看出该定理中的条件(~\ref{eq:theorem1}), 比引理~\ref{unique}的条件更强. 由$ \delta_S + \theta_{S,S} + \theta_{S,2S} < 1 $, 显然可以得到$ \delta_{2S} < 1 $. 实际上, 由引理~\ref{deltaandtheta}有
\begin{equation}
  \label{condition}
  \theta_{S,S} \leq \delta_{2S} \leq \theta_{S,S} + \delta_{S}
\end{equation}
由于$ \theta_{S,2S} \geq 0 $, 所以,
\[
\delta_{2S} \leq \theta_{S,S} + \delta_{S} + \theta_{S,2S} \leq 1
\]
另外, 如果给出条件$ \delta_S + \delta_{2S} + \delta_{3S} < 1 $, 则可以得到定理中的条件(~\ref{eq:theorem1})$ \delta_S + \theta_{S,S} + \theta_{S,2S} < 1 $.
因为
\[
\theta_{S,2S} \leq \delta_{3S} \leq \theta_{S,2S} + \max(\delta_{S}, \delta_{2S})
\]
再与式(~\ref{condition})不等号两边相加, 可以得到
\[
\theta_{S,S} + \theta_{S,2S} \leq \delta_{2S} + \delta_{3S}
\]所以, 不等式两边同时加上$ \delta_{S} $可以得到
\[
\delta_{S} + \theta_{S,S} + \theta_{S,2S} \leq \delta_{S} + \delta_{2S} + \delta_{3S}
\]

同时, 该定理不是以很高的概率满足最小解d=c, 而给出的是确定性的结果. 换句话说, 只要该定理的条件满足, 就一定能准确恢复出原向量c, 不会出现最小解d与c不同的情况.


\section{证明}
\label{sec:proof}

\subsection{引理~\ref{unique}的证明}
\label{sec:plemma1}

证明在$ \delta_{2S} < 1 $的条件下, 最小解具有唯一性, 用反证法. \\
假设存在两个不相同的稀疏解$ c,c' $, 其中$ c, c'$的支撑集$ T, T' $分别满足$ |T|, |T'| \leq S$, 使$ f = Fc = Fc' $, 则
\[
F(c - c') = 0
\]
由限制等距常数的定义, $ F(c - c') $满足(~\ref{eq:delta})式
\[
(1 - \delta_{2S}) \| c - c' \| \leq |\ F(c - c') \| \leq (1 + \delta_{2S}) \| c - c' \|
\]
因为$ \| F(c - c') \| = \| 0 \| = \mathbf{0} $, 所以
\[
(1 - \delta_{2S}) \| c - c' \| \leq 0 \leq (1 + \delta_{2S}) \| c - c' \|
\]
即
\[
\left\{
  \begin{array}{c}
    (1 - \delta_{2S}) \| c - c' \| \leq 0 \\
    (1 + \delta_{2S}) \| c - c' \| \geq 0 \\
  \end{array}
\right .
\]
已知$ 0 \leq \delta_{2S} < 1 $, 所以$ (1 \pm \delta_{2S}) > 0 $, 则有
\[
\left\{
  \begin{array}{c}
    \| c - c' \| \leq 0 \\
    \| c - c' \| \geq 0 \\
  \end{array}
\right .
\]
即
\begin{equation}
  \label{eq:norm}
  \| c - c' \| = 0
\end{equation}
而由向量2范数的定义
\[
\| \alpha \|_{\ell_2} = ( \sum_{i = 0}^n | a_i |^2 )^{1/2}
\]
因为分量$ | a_i |^2 \geq 0 $, 所以要$ | a_i |^2 = 0 $, 必须$ a_i = 0 $. \\
所以如果
\[
\| \alpha \|_{\ell_2} = 0
\]
就必有
\[
a_i = 0, \quad i = 0, 1, \dots, n.
\]
所以由式(~\ref{eq:norm})可得
\[
c_i - c_i' = 0, \quad i = 0, 1, \dots, n.
\]
即
\[ c = c' \]
与假设有两个不同的稀疏解矛盾, 所以当$ \delta_{2S} < 1$时, $(P_0)$具有唯一解. 证毕.


\subsection{定理~\ref{th:theorem1}的证明}
\label{sec:ptherem1}



如果可以找到向量$w$只要满足下面两个条件:
\begin{enumerate}
\item $ \left< w, v_j \right> = sgn( c_j ), \forall j \in T $
\item $ |\left< w, v_j \right>| < 1, \forall j \notin T $
\end{enumerate}
其中, $ sgn(c_j) $表示元素$ c_j $的符号, $ c_j = 0$时, $ sgn(c_j) = 0 $

就可以由$ (P_1) $唯一的最小解得到c. 

\begin{lemma}
  \label{le:relation}
  设$ S \geq 1 $,且$ \delta_S + \theta_{S,2S} < 1 $, 实向量c是支撑集为$ T \subseteq J, |T| \leq S $. 则存在一个向量$ w \in H $, 使得
  \begin{enumerate}
  \item $ \langle w, v_j \rangle = c_j, \quad \forall j \in T $
  \item $ |\langle w, v_j \rangle| \leq \frac{\theta_S}{(1 - \delta_S -\theta_{S,2S}) \sqrt{S}} \cdot \| c \|, \quad \forall j \notin T $
  \end{enumerate}
\end{lemma}
在引理中, 隐含的条件是$\sum_{j \in T} |c_j|^2 = 1 $.

注意: 上面两个条件和定理~\ref{th:theorem1}中的条件的关系可以由引理~\ref{le:relation}得到:\\
如果已知$ \delta_S + \theta_{S,S} + \theta_{S,2S} < 1 $, 则$ |\langle w, v_j \rangle| < 1$. 因为
\[
\| c \| \leq \| sgn(c) \| = \sqrt{|T|} \leq \sqrt{S}
\]
所以,
\[
|\langle w, v_j \rangle| \leq \frac{\theta_S}{(1 - \delta_S -\theta_{S,2S}) \sqrt{S}} \cdot \| c \| \leq \frac{\theta_S}{(1 - \delta_S -\theta_{S,2S}) \sqrt{S}} \cdot \sqrt{|T|} \leq \frac{\theta_S}{(1 - \delta_S -\theta_{S,2S})}
\]
如果$ \delta_S + \theta_{S,S} + \theta_{S,2S} < 1 $, 则$ \theta_{S,S} < 1 - \delta_S - \theta_{S,2S} $
即
\[
\frac{\theta_S}{(1 - \delta_S -\theta_{S,2S})} < 1
\]
所以, $|\langle w, v_j \rangle| < 1$.

现在给出定理~\ref{th:theorem1}的证明:\\
设至少存在一个$ (P_1) $的最小解$ d = (d_j)_{j \in J} $, 如果能证明$ d = c $, 即能证明. 由引理~\ref{unique}可以知道最小解是唯一的.

因为c的支撑集为T, 所以d满足
\begin{equation}
  \label{eq:pro}
  \| d \|_{\ell_1} \leq \| c \|_{\ell_1} = \sum_{j \in T} | c_j |
\end{equation}
取一个向量w满足1.和2.的两个条件, 则有

\begin{eqnarray*}
  \| d \|_{\ell_1} & = & \sum_{j \in T} |d_j| + \sum_{j \notin T} | d_j | \\
  & = & \sum_{j \in T} | c_j + (d_j - c_j) | + \sum_{j \notin T} | d_j | \\
\end{eqnarray*}
因为$ \left< w, v_j \right> = sgn( c_j ), \forall j \in T $和$ |\left< w, v_j \right>| < 1, \forall j \notin T $, 所以
\[
| c_j + (d_j - c_j) | \geq sgn(c_j)(c_j + (d_j - c_j)) 
\]
\[
| d_j | \geq d_j \geq d_j \left< w, v_j \right>
\]
即
\begin{eqnarray*}
  \| d \|_{\ell_1} & \geq & \sum_{j \in T} sgn(c_j)( c_j + (d_j - c_j) ) + \sum_{j \notin T}  d_j \left< w, v_j \right> \\
  & = & \sum_{j \in T} sgn(c_j) c_j + \sum_{j \in T} sgn(c_j) (d_j - c_j) + \sum_{j \notin T} d_j \left< w, v_j \right> \\
  & = & \sum_{j \in T} | c_j | + \sum_{j \in T} (d_j - c_j) \left< w, v_j \right> + \sum_{j \notin T} d_j \left< w, v_j \right> \\
  & = & \sum_{j \in T} | c_j | + \sum_{j \in T} d_j \left< w, v_j \right> - \sum_{j \in T} c_j \left< w, v_j \right> + \sum_{j \notin T} d_j \left< w, v_j \right> \\
  & = & \sum_{j \in T} | c_j | + \sum_{j \in J} d_j \left< w, v_j \right> - \sum_{j \in T} c_j \left< w, v_j \right> \\
  & = & \sum_{j \in T} | c_j | + \left< w, v_j \right> (\sum_{j \in J} d_j  - \sum_{j \in T} c_j ) \\
  & = & \sum_{j \in T} | c_j | + \langle w, v_j(\sum_{j \in J} d_j  - \sum_{j \in T} c_j ) \rangle \\
  & = & \sum_{j \in T} | c_j | + \langle w, \sum_{j \in J} d_j v_j  - \sum_{j \in T} c_j v_j \rangle \\
  & = & \sum_{j \in T} | c_j | + \langle w, f - f \rangle \\
  & = & \sum_{j \in T} | c_j |
\end{eqnarray*}
综合式(~\ref{eq:pro}), 可得
\[
\| d \|_{\ell_1} = \| c \|_{\ell_1}
\]
因为对于$\forall j \notin T , |\langle w, v_j \rangle| < 1 $, 这使得$j \notin T $时, $ d_j = 0 $.\footnote{为什么呢?} 因此
\[
F_T(d - c) = \sum_{j \in T}(d_j - c_j) = f - f = 0
\]
可以用证明引理~\ref{unique}的方法得到对于$\forall j \in T, d_j = c_j$, 所以$ d = c $. 即证.


% \begin{figure}
%   \centering
%   \includegraphics[width=1\textwidth]{/home/xls/Documents/Unix/tex/matrix_theory/linearsystem.png}
%   \caption{图}
% \end{figure}

\bibliography{../mybib}{}
\bibliographystyle{plain}


\end{document}
